#leetcode题目37：解数独
#难度：困难
#时间复杂度：O(n^2)
#空间复杂度：O(n^2)
#方法：回溯,dfs,递归


from typing import List
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        if not board:
            return

        line=[[False]*9 for _ in range(9)]
        col=[[False]*9 for _ in range(9)]
        box=[[[False]*9 for _a in range(3)] for _b in range(3)]
        space=[]
        valid=False

        for i in range(9):
            for j in range(9):
                if board[i][j]==".":
                    space.append((i,j))
                else:
                    n=int(board[i][j])-1
                    line[i][n]=col[j][n]=box[i//3][j//3][n]=True
        def dfs(pos):
            nonlocal valid #使valid为全局变量
            if pos==len(space):
                valid=True
                return
            i,j=space[pos]

            for x in range(9):
                if line[i][x]==col[j][x]==box[i//3][j//3][x]==False:
                    line[i][x]=col[j][x]=box[i//3][j//3][x]=True
                    board[i][j]=str(x+1)
                    dfs(pos+1)

                    line[i][x]=col[j][x]=box[i//3][j//3][x]=False
                if valid:
                    return
        dfs(0)

#测试数据
board=[
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
#预期输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
solution=Solution()
solution.solveSudoku(board)
print(board)